package org.datastructure.ReviewSort;

import java.util.Arrays;

/**
 * 排序复习
 */
public class Chapter7 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 10, 6, 9, 1, 4};
//        bubbleSort(arr);
//        selectSort(arr);
//        insertSort(arr);
//        shellSort1(arr);
//        shellSort2(arr);
//        quickSort(arr, 0, arr.length - 1);
//        quickSort1(arr, 0, arr.length - 1);
//        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
        radixSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void bubbleSort(int... arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int stemp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = stemp;
                }
            }
        }
    }

    public static void selectSort(int... arr) {
        int minIndex = 0;
        int minVal = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            minVal = arr[i];
            for (int j = i; j < arr.length; j++) {
                if (minVal > arr[j]) {
                    minVal = arr[j];
                    minIndex = j;
                }
            }
            // TODO: 前提是val=最小数，minIndex=最小数索引 
            // TODO: 将arr[i]赋值给找到的最小数
            arr[minIndex] = arr[i];
            // TODO: 将最小数赋值给arr[i] 
            arr[i] = minVal;
        }
    }

    public static void insertSort(int... arr) {
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            // TODO:  insertIndex小于0或insertVal等于或大于arr[insrtIndex]就退出 
            // TODO: 特殊的是等于，那么就退出，并且也不再交换了，让i+1继续下一个无序元素的比较
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if ((insertIndex + 1) != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

    public static void shellSort1(int[] arr) {
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    if (arr[j] > arr[j + step]) {
                        int stemp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = stemp;
                    }
                }
            }
        }
    }

    public static void shellSort2(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                insertVal = arr[i];
                insertIndex = i - step;

                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + step] = arr[insertIndex];
                    insertIndex -= step;
                }

                if (insertIndex + step != i) {
                    arr[insertIndex + step] = insertVal;
                }
            }
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int radix = 0;
        if (l < r) {
            radix = arr[l];
            while (l < r) {
                while (l < r && arr[r] >= radix) r--;
                arr[l] = arr[r];

                while (l < r && arr[l] <= radix) l++;
                arr[r] = arr[l];
            }

            arr[l] = radix;
            quickSort(arr, left, l - 1);
            quickSort(arr, l + 1, right);
        }
    }

    public static void quickSort1(int[] arr, int left, int right) {
        int l = left, r = right, mid = arr[(left + right) / 2];
        if (l < r) {
            while (l < r) {
                while (arr[r] > mid) r--;
                while (arr[l] < mid) l++;
                if (l == r) break;

                int stemp = arr[l];
                arr[l] = arr[r];
                arr[r] = stemp;
                if (arr[r] == mid) l++;
                if (arr[l] == mid) r--;
            }
            if (r == l) {
                r--;
                l++;
            }
            quickSort1(arr, left, r);
            quickSort1(arr, l, right);
        }
    }

    public static void mergeSort(int[] arr, int left, int right, int[] stemp) {
        int mid = (left + right) / 2;
        if (left < right) {
            mergeSort(arr, left, mid, stemp);
            mergeSort(arr, mid + 1, right, stemp);
            merge(arr, left, mid, right, stemp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] stemp) {
        int i = left;
        int j = mid + 1;
        int index = 0;

        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                stemp[index++] = arr[i++];
            } else {
                stemp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            stemp[index++] = arr[i++];
        }
        while (j <= right) {
            stemp[index++] = arr[j++];
        }
        index = 0;
        while (left <= right) {
            arr[left++] = stemp[index++];
        }
    }

    public static void radixSort(int[] arr) {
        int bucketElementCount[] = new int[10];
        int[][] buckets = new int[10][arr.length];
        int length = (Arrays.stream(arr).max().getAsInt() + "").length();

        int elementOfBucket = 0;
        for (int l = 0, n = 1; l < length; n *= 10, l++) {
            for (int i = 0; i < arr.length; i++) {
                elementOfBucket = arr[i] / n % 10;
                buckets[elementOfBucket][bucketElementCount[elementOfBucket]++] = arr[i];
            }
            int index = 0;
            for (int i = 0; i < bucketElementCount.length; i++) {
                if (bucketElementCount[i] != 0) {
                    for (int j = 0; j < bucketElementCount[i]; j++) {
                        arr[index++] = buckets[i][j];
                    }
                }
                bucketElementCount[i] = 0;
            }
        }
    }


}
